`
https://leetcode.cn/problems/ugly-number-iii/
`

/**
 * @param {number} n
 * @param {number} a
 * @param {number} b
 * @param {number} c
 * @return {number}
 */
var nthUglyNumber = function (n, a, b, c) {

  // 计算 <= x 的丑数个数是否 >= n
  const check = (x) =>
    // A + B + C - A ∩ B - A ∩ C - B ∩ C + A ∩ B ∩ C
    Math.floor(x / a)
    + Math.floor(x / b)
    + Math.floor(x / c)
    - Math.floor(x / lcm(a, b))
    - Math.floor(x / lcm(a, c))
    - Math.floor(x / lcm(b, c))
    + Math.floor(x / lcm(lcm(a, b), c)) >= n

  // a, b, c 最小值是 min(a, b, c)，第 n 个丑数至少是 min(a, b, c) + n − 1，再减一就一定无法满足要求
  let left = Math.min(a, b, c) + n - 2
  let right = Math.min(a, b, c) * n
  while (left + 1 < right) {
    const mid = left + Math.floor((right - left) / 2)
    if (check(mid)) {
      right = mid
    } else {
      left = mid
    }
  }
  return right
};

function gcd(a, b) {
  a = Math.abs(a);
  b = Math.abs(b);
  while (b !== 0) {
    [a, b] = [b, a % b];
  }
  return a;
}

function lcm(a, b) {
  return Math.abs(a * b) / gcd(a, b);
}